\section{Introduction}
\label{sec:intro}

Consider a bipartite graph $G=(V,W,E)$, where $|V|,|W|=n$. Suppose
every $k$ element subset $S \subseteq V$ is connected to every $k$
element subset $T \subseteq W$ by at least one edge. How many edges
must such a graph have? This is the celebrated Zarankiewicz
problem. 
%(The Zarenkiewicz problem is more commonly posed in the
%following form: What is the maximum number of edges in an $n\times n$
%bipartite graph with no bipartite clique $K_{k,k}$?  For our purposes,
%the complementary form will be more convenient.)

\begin{definition}[Bipartite independent set]
A bipartite independent set of size $k \times k$ in a bipartite graph
$G=(V,W,E)$ is a pair of subsets $S \subseteq V$ and $T \subseteq W$
of size $k$ each such that there is no edge connecting $S$ and $T$, i.e.,
$(S \times T) \cap E = \emptyset$.
\end{definition}

\noindent The Zarankiewicz problem asks for the minimum number of edges in
a bipartite graph that does not have any bipartite independent set of
size $k \times k$. We may think of an edge as a complete bipartite
graph where each side of the bipartition is just a singleton. This
motivates the following generalization where we consider bipartite
graphs as formed by putting together not just edges, but, more
generally, small complete bipartite graphs.

\begin{definition}
A bipartite graph $G=(V,W,E)$ is said to be the union of complete
bipartite graphs $G_i=(V_i,W_i,E_i=V_i \times W_i)$, ($i=1,2,\ldots,
r$) if each $V_i \subseteq V$, each $W_i \subseteq W$, and
$E = E_1 \cup \cdots  \cup E_r$. 
\end{definition}

\begin{definition}
We say that a sequence of positive integers $(n_1,n_2,\ldots,n_r)$ is
$(n,k)$-strong if there is a bipartite graph $G=(V,W,E)$ that is a
union of graphs $G_i=(V_i,W_i, E_i=V_i \times W_i)$, $i=1,2,\ldots,r$,
such that
\begin{itemize}
\item $|V|, |W|=n$;
\item $|V_i|=|W_i|=n_i$;
\item $G$ has no bipartite independent set of size $k \times k$.
\end{itemize}
\end{definition}

\noindent What conditions must the $n_i$'s satisfy for
$(n_1,n_2,\ldots,n_r)$ to be $(n,k)$-strong?  Note that the
Zarankiewicz problem is a special case of this question where each
$n_i$ is $1$ and $\sum_i {n_i}$ corresponds to the number edges in the
final graph $G$.

\paragraph*{\bf Remark.} The Zarankiewicz 
problem is more commonly posed in the following form: What is the
maximum number of edges in a bipartite graph with no $k \times k$
bipartite {\em clique}. By interchanging edges and non-edges, we can
ask for the maximum number of non-edges (equivalently the minimum
number of edges) such that there is no $k \times k$ bipartite {\em
independent set}. This complementary form is more convenient for our
purposes.

%\paragraph*{\bf Remark.} Given $n_i$'s, the choice of $G_i$'s also
%determines whether or not $G$ has an independent set of a given
%size. If $(n_1,n_2,\ldots,n_r)$ is $(n,k)$-strong, it implies that
%there is {\em some} choice of $G_i$'s for which the union graph $G$
%does not have any independent set of size $k \times k$.

\paragraph*{\bf The K\H{o}v\'{a}ri, S\'{o}s and Tur\'{a}n bound \\}

The following classical theorem gives a lower bound on the number of
edges in that have no large independent set.

\begin{theorem}[K\H{o}v\'{a}ri, S\'{o}s and Tur\'{a}n~\cite{KST};
see, e.g., \cite{bollobas}, Page 301, Lemma 2.1.] 
\label{thm:kst}
If $G$ does not have an independent set of size $k\times k$, then
\[    n  {{n-{\overline d}} \choose k} {n \choose k}^{-1} \leq k-1, \]
where $\overline{d}$ is the average degree of $G$.
\end{theorem}
\noindent The above theorem implies that 
\begin{eqnarray*}
n &\leq& (k-1) {{n-{\overline d}} \choose k}^{-1} {n \choose k} \\ 
  &\leq& (k-1) \left(\frac{n-k+1}{n-\overline{d}-k+1}\right)^k \\ 
  &=&    (k-1) \left(1+\frac{\overline{d}}{n-\overline{d}-k+1}\right)^k \\ 
  &\leq& (k-1) \exp\left(\frac{\overline{d}k}{n-\overline{d}-k+1}\right),
\end{eqnarray*}
which yields,
\[ \overline{d} \geq \frac{(n-k+1)\log (n/(k-1))}{k + \log (n/(k-1))}.\]
In this paper, we will mainly be interested in $k \in [n^{1/10},
  n^{9/10}]$, in which case we obtain
\[  |E(G)| = n \overline{d} = \Omega\left(\frac{n^2}{k} \log n \right). \]
For the problem under consideration, this immediately gives the
necessary condition
\begin{equation}
\label{eq:kst-edges}
 \sum_{i=1}^r n_i^2 = \Omega\left(\frac{n^2}{k} \log n \right). 
\end{equation}
It will be convenient to normalize $n_i$ and define $\alpha_i =
\frac{n_i}{n/k}$. With this notation, the inequality above can be 
restated as follows.
\begin{equation}
\label{eq:kst}
 \sum_{i=1}^r \alpha_i^2 = \Omega(k \log n).
\end{equation}

\paragraph*{\bf The Hansel bound \\} 

The same question can also be asked in the context of general
graphs. In that case, we have the classical theorem.

\begin{theorem}[Hansel~\cite{Hansel}, Katona and Szemer\'{e}di~\cite{KSz}]
\label{thm:hansel}
Suppose it is possible to place one copy each of $K_{n_i,n_i}$,
$i=1,2,\ldots,r$, in a vertex set of size $n$ such that the
resulting graph has no independent set of size $k$. Then,
\[ \sum_{i=1}^r n_i \geq n \log \left( \frac{n}{k-1} \right). \]
\end{theorem}

\noindent Although this result pertains to general graphs and is not
directly applicable to the bipartite graph setting, it can be used
(details omitted as we will use this bound only to motivate our
results, not to derive them) to derive a necessary condition for
bipartite graphs as well. In particular, normalizing $n_i$ by setting
$n_i = \alpha_i\frac{n}{k}$ as before, one can obtain the necessary
condition
\begin{equation}
\label{eq:hansel}
 \sum_{i=1}^r \alpha_i = \Omega(k \log n).
\end{equation}

Note that neither of the two bounds above strictly dominates the
other: if all $\alpha_i$ are small (say $\ll 1$), then the first
condition derived from the K\H{o}v\'{a}ri, S\'{o}s and Tur\'{a}n bound
is stronger, wheras if all $\alpha_i$ are large ($\gg 1$), then the
condition derived from the Hansel bound is stronger.

In our applications, we will meet situations where the $\alpha_i$'s
will not be confined to one or the other regime. To get optimal
results, one must, therefore, devise a condition appropriate for the
entire range of values for the $\alpha_i$'s. Towards this goal, we
start by trying to guess the form of this general inequality by asking
a dual question: what is a sufficient condition on $n_i$'s
(equivalently $\alpha_i$'s) for $(n_1,n_2,\ldots,n_r)$ to be
$(n,k)$-strong? We derive the following.

\begin{theorem}[Sufficient condition]
\label{thm:sufficient.symmetric}
Suppose $k \in [n^{1/10}, n^{9/10}]$, and let $\alpha_i \in
[n^{-1/100}, n^{1/100}]$, $i=1,2\ldots,r$. Then, there is a constant $A > 0$
such that if
\[ \sum_{i: \alpha_i \leq 1} \alpha_i^2 + \sum_{i: \alpha_i > 1} \alpha_i \geq A k \log n,\]
then $(n_1,n_2,\ldots,n_r)$ is $(n,k)$-strong, where $n_i = \alpha_i
(n/k)$.
\end{theorem}

\noindent Using this insight, we then show that this sufficient condition is
indeed also necessary (with slightly different constants).

\begin{theorem}[Necessary condition]
\label{thm:necessary.symmetric}
Suppose $k \in [n^{1/10}, n^{9/10}]$, and let $\alpha_i \in
[n^{-1/100}, n^{1/100}]$, $i=1,2\ldots,r$. Then, there is a constant
$B > 0$ such that if $(n_1,n_2,\ldots,n_r)$ is $(n,k)$-strong where $n_i =
\alpha_i (n/k)$, then
\[ \sum_{i: \alpha_i \leq 1} \alpha_i^2 + \sum_{i: \alpha_i > 1} \alpha_i \geq B k \log n.\]
\end{theorem}

%\paragraph*{\bf Remark.} A weaker version of this necessary condition
%was employed by Radhakrishnan and Ta-Shma~\cite{RT} in the proof of
%the optimal lower bound on the size of depth-two
%superconcentrators. They showed that (for some constant $D$), if
%$\sum_{i: \alpha_i > 1} \alpha_i \leq D k \log n$, then $\sum_{i:
%\alpha_i \leq 1} \alpha_i^2 \geq D k$ (with the $\log n$ missing on
%the right hand side).

\noindent Our proof of Theorem~\ref{thm:necessary.symmetric} uses a
refinement of the ideas used in Radhakrishnan and Ta-Shma~\cite{RT}.
In a later section, we also show that our inequality leads to a
modular proof of their tight lower bound on the size of depth-two
superconcentrators.

A tradeoff result for depth-two superconcentrators was shown by Dutta
and Radhakrishnan~\cite{DR}. Their main argument leads one to consider
situations where the small bipartite graphs used to build the bigger
one are not symmetric, instead of being of the form $K_{n_i,n_i}$,
they are of the form $K_{m_i,n_i}$ (with perhaps $m_i \neq n_i$).

\begin{definition}
We say that a sequence of pairs of positive integers
$((m_1,n_1),(m_2,n_2),\ldots,(m_r,n_r))$ is $(n,k)$-strong if there is
a bipartite graph $G=(V,W,E)$ that is a union of graphs $G_i=(V_i,W_i,
E_i=V_i \times W_i)$, $i=1,2,\ldots,r$, such that
\begin{itemize}
\item $|V|, |W|=n$;
\item $|V_i|=m_i$ and $|W_i|=n_i$.
\item $G$ has no bipartite independent set of size $k \times k$.
\end{itemize}
\end{definition}

\noindent We refine our arguments and provide tight necessary and
sufficient conditions for this asymmetric setting as well. From the
necessary condition for the asymmetric setting, we derive the tradeoff
result shown earlier by Dutta and Radhakrishnan~\cite{DR}. Our main
results are the following.

\begin{theorem}[Sufficient condition: asymmetric case]
\label{thm:sufficient.asymmetric}
Suppose $k \in [n^{1/10}, n^{9/10}]$, and let $\alpha_i, \beta_i \in
[n^{1/100}, n^{-1/100}]$, $i=1,2\ldots,r$.  Then, there is a constant
$C > 0$ such that if
%\[ \sum_{i: \min\{\alpha_i, \beta_i\} \leq 1} \alpha_i \beta_i + \sum_{i: \min\{\alpha_i, \beta_i\} > 1} (\alpha_i + \beta_i) \ent(p_i) \geq C k \log n \]
\[ \sum_{i \in X} \alpha_i \beta_i + \sum_{i \in \{1,2,\ldots,r\} \setminus X} (\alpha_i + \beta_i) \ent(p_i) \geq C k \log n \]
for every $X \subseteq \{1,2,\ldots,r\}$, where $p_i =
\frac{\alpha_i}{\alpha_i + \beta_i}$ and $\ent(p_i) = -p_i \log(p_i) -
(1-p_i) \log(1-p_i)$ is the binary entropy function, then the sequence
$((m_1,n_1),(m_2,n_2),\ldots,(m_r,n_r))$ is $(n,k)$-strong where $m_i
= \alpha_i (n/k)$, $n_i = \beta_i (n/k)$.

\end{theorem}

\begin{theorem}[Necessary condition: asymmetric case]
\label{thm:necessary.asymmetric}
Suppose $k \in [n^{1/10}, n^{9/10}]$, and let $\alpha_i, \beta_i \in
[n^{-1/100}, n^{1/100}]$, $i=1,2\ldots,r$. Then, there is a constant
$D > 0$ such that if the sequence $((m_1,n_1),(m_2,n_2),\ldots,(m_r,n_r))$
is $(n,k)$-strong where $m_i = \alpha_i (n/k)$ and $n_i = \beta_i
(n/k)$, then
%\[ \sum_{i: \min\{\alpha_i, \beta_i\} \leq 1} \alpha_i \beta_i + \sum_{i: \min\{\alpha_i,\beta_i\} > 1} (\alpha_i + \beta_i) \ent(p_i) \geq D k \log n, \]
\[ \sum_{i \in X} \alpha_i \beta_i + \sum_{i \in \{1,2,\ldots,r\} \setminus X} (\alpha_i + \beta_i) \ent(p_i) \geq D k \log n \]
for every $X \subseteq \{1,2,\ldots,r\}$, where $p_i =
\frac{\alpha_i}{\alpha_i + \beta_i}$ and $\ent(p_i) = -p_i \log(p_i) -
(1-p_i) \log(1-p_i)$.
\end{theorem}

\subsection*{Organization}
In Section~\ref{sec:symmetric}, we first derive the sufficient
condition (Theorem~\ref{thm:sufficient.symmetric}) and then prove the
necessary condition (Theorem~\ref{thm:necessary.symmetric}) for the
symmetric setting.  We then present generalizations of these results
to the asymmetric setting in Section~\ref{sec:asymmetric}. In
Section~\ref{sec:superconcentrator}, we derive the depth-two
superconcentrator results.
